#include "sort.h"

void _QuickSort(vector<int>& vc, int begin, int end);
int Segment(vector<int>& vc, int begin, int end);
int GetMidIndex(vector<int>& vc, int left, int right);

static void InsertSort(vector<int>& vc, int left, int right){
  for(int i=left; i<right-1; ++i)
  {
    int end = i;
    int tmp = vc[end+1];
    while(end >= left){
      if(tmp < vc[end])
      {
        vc[end+1] = vc[end];
        --end;
      }
      else
      {
        break;
      }
    }
    vc[end+1] = tmp;
  }
}

//void QuickSort(vector<int>& vc){
//  _QuickSort(vc, 0, vc.size()); 
//}

void QuickSort(vector<int>& vc){
  stack<int> st;
  st.push(0);
  st.push(vc.size());
  while(!st.empty())
  {
    int end = st.top();
    st.pop();
    int begin = st.top();
    st.pop();

    if(end-begin<15)
    {
      InsertSort(vc, begin, end);
      continue;
    }

    int div = Segment(vc, begin, end);
    if(div - begin > 1)
    {
      st.push(begin);
      st.push(div);
    }
    if(end - (div+1) > 1)
    {
      st.push(div+1);
      st.push(end);
    }
  }
}

void _QuickSort(vector<int>& vc, int begin, int end){
  if(end-begin<15)
  {
    InsertSort(vc, begin, end);
    return;
  }
  int div = Segment(vc, begin, end);
  if(div - begin > 1)
  {
    _QuickSort(vc, begin, div);
  }
  if(end - (div+1) >1)
  {
    _QuickSort(vc, div+1, end);
  }
}

int Segment(vector<int>& vc, int begin, int end){
  int midi = GetMidIndex(vc, begin, end-1); 
  swap(vc[begin], vc[midi]);
  int keyi = begin;
  int prev = begin;
  int cur = begin+1;
  while(cur < end)
  {
    if(vc[cur] < vc[keyi] && cur != ++prev)
    {
      swap(vc[cur], vc[prev]);
    }
    ++cur;
  }
  swap(vc[prev], vc[keyi]);
  return prev;
}

int GetMidIndex(vector<int>& vc, int left, int right){
  int midi = left+(right-left)/2;
  int tmp1 = vc[left] > vc[midi]? left:midi;
  int tmp2 = vc[right] > vc[midi]? right:midi;
  return vc[tmp1] > vc[tmp2]? tmp2:tmp1;
}

